题目分析

最近的题目是哈希表专题，希望小伙伴能够坚持练习，这个问题难度不大，先认真思考5分钟，看一看能够想出多少种解法。

暴力法

枚举起点和终点，计算区间内0和1的个数是否相等。这个思路最容易想到，但是时间复杂度最高。

此题可以进行稍微优化，因为要求最长的连续子数组，因此可以按照长度从大到小进行遍历。

算法的**时间复杂度为$O(n^3)$，空间复杂度为$O(1)$**。

class Solution(object):
    def findMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for interval in range(len(nums), -1, -1):
            if not interval % 2:
                for i in range(len(nums) - interval + 1):
                    if len([1 for j in range(i, i + interval) if nums[j] == 0]) == interval / 2:
                        return interval

优化暴力法

利用前缀和的特点，计算区间内0和1个数时，节省一层循环。但是要牺牲一些空间复杂度用于存放前缀和。

算法的**时间复杂度为$O(n^2)$，空间复杂度为$O(n)$**。

class Solution(object):
    def findMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cursum = [0]
        for i in range(len(nums)):
            cursum.append(cursum[-1] + nums[i])
        for interval in range(len(nums), -1, -1):
            if not interval % 2:
                for i in range(len(nums) - interval + 1):
                    if cursum[i + interval] - cursum[i] == interval / 2:
                        return interval

哈希表

根据一般性规律，我们可以从题目中寻找一些提示。算法一般能够接受的时间复杂度再1e8以内，而这个题目的长度可以达到50000，因此使用$O(n^2)$的时间复杂度都会TLE。因此我们要想出一些$O(n)$或者$O(nlog(n))$的算法进行求解。

数量相同的0和1是包含着一些规律的，如果出现0则计数加1，出现1则计数减1，那么这个计数代表着0和1的相对差。如果i处和j处的相对差相等，说明从i+1到j的序列中0和1的个数是相同的。

我们只需要记录每个绝对差第一次出现的索引i，如果出现相等的绝对差，则记录长度，求出最大的长度即可。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

class Solution(object):
    def findMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cur, dic, max_val = 0, {0: -1}, 0
        for i, v in enumerate(nums):
            if v == 0:
                cur += 1
            else:
                cur -= 1
            if cur in dic:
                max_val = max(max_val, i - dic[cur])
            else:
                dic[cur] = i
        return max_val

刷题总结

有感而发~，随着内卷越来越严重，公司对人才的要求也越来越苛刻，小伙伴们如果想要大的平台和更多的机遇，一定要加强代码能力，有些人就会说这有什么用？当你做的题目足够多的时候，就会慢慢的察觉到它的作用。